package com.demo.sort;

import com.demo.sort.base.SortBase;

import java.util.Arrays;

/**
 * 堆排序
 * 堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
 *
 * 思路:
 * 1.
 **/
public class HeapSort extends SortBase {

    @Override
    public int[] sort(int[] init) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(init, init.length);
        int len = arr.length;
        buildMaxHeap(arr, len);
        for(int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    private void buildMaxHeap(int[] arr, int len) {
        for(int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // 基数下标
        int largest = i;

        // 得到三数比较后最大值下标
        {
            if (left < len && arr[left] > arr[largest]) {
                largest = left;
            }

            if (right < len && arr[right] > arr[largest]) {
                largest = right;
            }
        }

        if (largest != i) {
            // i下标元素为  三数比较最大的值
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }
}
